package newBee.class1;

import common.ArrayUtils;

/**
 * https://leetcode.cn/problems/daily-temperatures/?envType=problem-list-v2&envId=monotonic-stack
 * 每日温度
 * 解题思路：
 * 小压大，当栈被弹出时，能获得最近一次高于当前温度
 */
public class Code03_dailyTemperatures {
    public static void main(String[] args) {
        int[] temperatures = {89, 62, 70, 58, 47, 47, 46, 76, 100, 70};
        int[] ans = dailyTemperatures(temperatures);
        ArrayUtils.printArr(ans);
    }

    /**
     * 用array模拟栈操作
     */
    public static int[] dailyTemperatures(int[] arr) {
        // ans 为记录
        int[] ans = new int[arr.length], stack = new int[arr.length];
        int r = 0;
        for (int i = 0; i < arr.length; i++) {
            // 入栈前比较
            while (r > 0 && arr[stack[r - 1]] < arr[i]) {
                int k = stack[--r]; // 出栈
                ans[k] = i - k; // 计算相隔天数
            }
            // 入栈
            stack[r++] = i;
        }
        return ans;
    }
}